<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>tree-树</title>
</head>

<body>
    <script>
        // insert(key):向树中插入一个新的键。
        // search(key):在树中查找一个键，如果节点存在，则返回true;如果不存在，则返回false。
        // inOrderTraverse:通过中序遍历方式遍历所有节点。
        // preOrderTraverse:通过先序遍历方式遍历所有节点。
        // postOrderTraverse:通过后序遍历方式遍历所有节点。
        // min:返回树中最小的值/键。
        // max:返回树中最大的值/键。
        // remove(key):从树中移除某个键。

        // demo: https://www.cnblogs.com/tugenhua0707/p/4361051.html
        function BST() {
            this.root = null;
            this.insert = insert;
            this.inOrder = inOrder;
            this.getMin = getMin;
            this.getMax = getMax;
            this.find = find;
            this.remove = remove;
        }

        function Node(data, left, right) {
            this.data = data;
            this.left = left;
            this.right = right;
            this.show = show;
        }

        function show() {
            return this.data;
        }

        function insert(data) {
            var n = new Node(data, null, null);
            if (this.root == null) {
                this.root = n;
            } else {
                var current = this.root;
                var parent;
                while (current) {
                    parent = current;
                    if (data < current.data) {
                        current = current.left;
                        if (current == null) {
                            parent.left = n;
                            break;
                        }
                    } else {
                        current = current.right;
                        if (current == null) {
                            parent.right = n;
                            break;
                        }
                    }
                }
            }
        }
        // 中序遍历
        function inOrder(node) {
            if (!(node == null)) {
                inOrder(node.left);
                console.log(node.show());
                inOrder(node.right);
            }
        }

        // 先序遍历 
        function preOrder(node) {
            if (!(node == null)) {
                console.log(node.show());
                preOrder(node.left);
                preOrder(node.right);
            }
        }

        // 后序遍历
        function postOrder(node) {
            if (!(node == null)) {
                postOrder(node.left);
                postOrder(node.right);
                console.log("后序遍历" + node.show());
            }
        }

        // 二叉树查找最小值
        function getMin() {
            var current = this.root;
            while (!(current.left == null)) {
                current = current.left;
            }
            return current.data;
        }

        // 二叉树上查找最大值
        function getMax() {
            var current = this.root;
            while (!(current.right == null)) {
                current = current.right;
            }
            return current.data;
        }

        // 查找给定值
        function find(data) {
            var current = this.root;
            while (current != null) {
                if (current.data == data) {
                    return current;
                } else if (data < current.data) {
                    current = current.left;
                } else {
                    current = current.right;
                }
            }
            return null;
        }

        function remove(data) {
            root = removeNode(this.root, data);
        }
        function getSmallest(node) {
            if (node.left == null) {
                return node;
            }
            else {
                return getSmallest(node.left);
            }
        }
        function removeNode(node, data) {
            if (node == null) {
                return null;
            }
            if (data == node.data) {
                // 没有子节点的节点
                if (node.left == null && node.right == null) {
                    return null;
                }
                // 没有左子节点的节点
                if (node.left == null) {
                    return node.right;
                }
                // 没有右子节点的节点
                if (node.right == null) {
                    return node.left;
                }
                // 有2个子节点的节点
                var tempNode = getSmallest(node.right);
                node.data = tempNode.data;
                node.right = removeNode(node.right, tempNode.data);
                return node;
            } else if (data < node.data) {
                node.left = removeNode(node.left, data);
                return node;
            } else {
                node.right = removeNode(node.right, data);
                return node;
            }
        }
        // 代码初始化如下：
        var nums = new BST();
        nums.insert(23);
        nums.insert(45);
        nums.insert(16);
        nums.insert(37);
        nums.insert(3);
        nums.insert(99);
        nums.insert(22);
        var min = nums.getMin();
        console.log(min);
        var max = nums.getMax();
        console.log(max);
        var value = nums.find("45");
        console.log(value);
        nums.remove(23);
    </script>
</body>

</html>